package algebra.visitors;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

import algebra.OrderingDescription;
import algebra.ProjectionDescription;
import algebra.op.ProjectionQuery;

import kb.DescriptionLogicsKB;
import utils.Util;
import utils.exception.ProjectionException;
import utils.opt.CacheTree;
import entities.ConceptAssertion;
import entities.Individual;
import entities.StarConceptAssertion;
import entities.concept.AndConcept;
import entities.concept.Concept;
import entities.concept.DomainConceptEQ;
import entities.concept.DomainConceptLT;
import entities.concept.DomainConceptLTEQ;
import entities.concept.ExistsConcept;
import entities.concept.NotConcept;
//import entities.concept.NotConcept;
import entities.concept.OrConcept;
import entities.role.GeneralRolePath;
import entities.role.Role;
import entities.vocabulary.KBVocabulary;

public class ProjectionQueryVisitorEvaluator {
	public static final boolean allowMissingFeaturePatching = false;
	private static boolean ENABLE_OPTIMIZATIONS = true;
	private static boolean ENABLE_CACHETREE = true;
	private static int structuralSubsumptions = 0;
	private static final boolean ChooseLongestEqConcept = true;
	private DescriptionLogicsKB kb;
	private OrderingDescription od;
	

	public ProjectionQueryVisitorEvaluator(DescriptionLogicsKB kb, OrderingDescription od) {
		super();
		this.kb = kb;
		this.od = od;
	}
	
	
	public DescriptionLogicsKB getKB(){
		return this.kb;
	}
	
	public static int getStructuralSubsumptions() {
		return structuralSubsumptions;
	}
	
	
	
	/*
	 * Given (a:C, pd), compute a:LCS.
	 */
	public List<ConceptAssertion> visit(ProjectionQuery pq){
		List<ConceptAssertion> res = new LinkedList<ConceptAssertion>();
		ProjectionDescription pd = pq.getPrjDesc();
		QueryVisitorEvaluator eval = new QueryVisitorEvaluator(kb, od);
		List<ConceptAssertion> subres = pq.getSubquery().acceptVisitor(eval);
		if(QueryVisitorEvaluator.isSpecialAssertion(subres)){
			//star semantics, use a representative assertion for testing
			StarConceptAssertion sca = (StarConceptAssertion) subres.get(0);
			ConceptAssertion rep = new ConceptAssertion(Individual.getAnonIndividual(), sca.getConcept());
			try {
				res.add(projectFinal(rep, pd, null, true));
			} catch (ProjectionException e) {
				e.printStackTrace();
			}
		}else{
			//standard semantics
			for(ConceptAssertion ca:subres){
				try {
//					System.out.println("testing: "+ca);
					res.add(projectFinal(ca, pd, null, false));
				} catch (ProjectionException e) {
					e.printStackTrace();
				}
			}
		}
		return res;
	}
	
	private ConceptAssertion projectFinal(ConceptAssertion ca, ProjectionDescription pd, 
			GeneralRolePath grp, boolean star) throws ProjectionException{
		//star or standard semantics
		List<Concept> res = project(ca, pd, grp);
		Concept desc = null;
		if(res.size()>1){
			desc =  new AndConcept(res);
		}else if(res.size() == 1){
			desc = res.get(0);
		}else{
			desc = KBVocabulary.CONCEPT_TOP;
//			System.err.println("Nothing was projected. Exit."+res.size());
//			throw new RuntimeException();
		}
		
		Individual ind = null;
		if(star){
			ind = KBVocabulary.SPECIAL_IND;
		}else{
			ind = ca.getIndividual();
		}

		return new ConceptAssertion(ind, desc);
	}
	
	private List<Concept> project(ConceptAssertion ca, ProjectionDescription pd, GeneralRolePath grp) 
		throws ProjectionException {
		if (grp == null) {
			grp = new GeneralRolePath();
		}
		switch (pd.getType()) {
		case ProjectionDescription.CONCEPT:
			return projectConcept(ca, pd.getConcept(), grp);
		case ProjectionDescription.FEATURE:	
			return reduce(projectFeature(ca, pd.getArg(), grp), grp, this.kb);
		case ProjectionDescription.CONJUNCTION:
			return projectJoin(ca, pd.getPd1(), pd.getPd2(), grp);
		case ProjectionDescription.ROLE:
			return reduce(projectRole(ca, pd.getArg(), pd.getPd1(), grp), grp, this.kb);
		default:
			throw new ProjectionException("Unrecognized Projection Type: " + pd.getType() +"\n" + pd.toString());
		}
	}
	

	/**
	 * 
	 * @param ca: the condition
	 * @param c1: the projection description concept?
	 * @param rp: role path
	 * @param tb,ab: the knowledge base
	 * @return
	 */
	private List<Concept> projectConcept(ConceptAssertion ca, Concept c1, GeneralRolePath grp) {
		// Case 1. C under exists R. (C1), return {C1}
		List<Concept> result = new LinkedList<Concept>();
		Concept rhs = Util.parseConceptFromGeneralRolePath(grp, c1);
		ConceptAssertion ast = new ConceptAssertion(ca.getIndividual(), rhs);
		if (Util.assertionCheck(ca, ast,kb)) {
			result.add(c1);
			return result;
		}
		
		// Case 2. C under exists R. (T), return {T}
		if (grp.length() > 0) {
			rhs = Util.parseConceptFromGeneralRolePath(grp, KBVocabulary.CONCEPT_TOP);
			ast = new ConceptAssertion(ca.getIndividual(), rhs);
			if (Util.assertionCheck(ca, ast, kb)) {
				result.add(KBVocabulary.CONCEPT_TOP);
				return result;
			}
		}
		// Otherwise, return {}
		result.add(KBVocabulary.CONCEPT_TOP);
		return result;
	}

	
	
	private List<Concept> projectFeature(ConceptAssertion ca, String f, GeneralRolePath grp) 
		throws ProjectionException {
		List<Concept> result = new LinkedList<Concept>();
		if(ENABLE_CACHETREE){
			//retrieve the cache for possible matches
			HashSet<String> potres = CacheTree.findCacheForFeature(ca.getIndividual(), grp, new Role(f));
			if(potres.size()>0){
				System.out.println("Role path:"+grp+"; cache for "+f+": "+potres);
				List<String> listOfConstants = new ArrayList<String>();
				listOfConstants.addAll(potres);
				Collections.sort(listOfConstants, new Comparator<String>(){
					public int compare(String o1, String o2){
						return o1.compareTo(o2);
					}	
				});
				result.addAll(
						iterativeSearchK(ca, new Role(f), grp, listOfConstants, 0, listOfConstants.size()-1));
				//System.out.println(++CACHE_HIT);
				if(result.size()>0){
					//if no result found, resort to general reasoning
					//System.err.println("Error may be for :"+ca.getIndividual());
					return result;
				}
			}
		}
		
		// First try structural subsumption test 
		// (ie., look for feature 'f' explicitly appearing in 'C').
		if (ENABLE_OPTIMIZATIONS) {
			if (grp == null || grp.getOffset()==0) {
				LinkedList<GeneralRolePath> q = new  LinkedList<GeneralRolePath>();
				GeneralRolePath p = new GeneralRolePath();
				p.addContent(ca.getConcept());
				q.add(p);
				while (!q.isEmpty()) {
					p = q.remove();
					Concept con = (Concept) p.getLastItem();
					if (con instanceof AndConcept) {
						for (Concept and : ((AndConcept)con).getConceptSet()) {
							GeneralRolePath testrp = new GeneralRolePath();
							testrp.addContent(and);
							q.add(testrp);
						}
					}
					else if (con instanceof OrConcept) {
						for (Concept or : ((OrConcept)con).getConceptSet()) {
							GeneralRolePath testrp = new GeneralRolePath();
							testrp.addContent(or);
							q.add(testrp);
						}
					}
					else if (p.getOffset() == 0 && con instanceof DomainConceptEQ) {

						if (((DomainConceptEQ<?,?>)con).getFeature().toString().equals(f)) {
							structuralSubsumptions += 1;
							result.add(con);
						}
					}
				}
				//possibly more feature values are available in KB
				if (result.size() > 0) {
					return result;
				}
				
			}
		}
		
		// Resort to testing (f = k) for values of k in the data set. Binary search or scan for k.
//		Concept r = null;
//		if (rp.length() == 0) {
//			r = searchK(ca.getConcept(), new Role(f), rp, Util.getConstants(), 0, Util.getConstants().length);
//			//TODO: !!! optimization: update description to include 'r'
//		}
//		else {
//			result = scanK(ca.getConcept(), new Role(f), rp, Util.getConstants(), 0, Util.getConstants().length);
//		}
//		if (r != null) {
//			result.add(r);
//		}
		//added by Jiewen, new algorithm
		List<String> listOfConstants = Arrays.asList(Util.getConstants());
		Collections.sort(listOfConstants, new Comparator<String>(){
			public int compare(String o1, String o2){
				return o1.compareTo(o2);
			}	
		});

		result.addAll(
				iterativeSearchK(ca, new Role(f), grp, listOfConstants, 0, listOfConstants.size()-1));

		if (result.size() == 0) {
			result.add(KBVocabulary.CONCEPT_TOP);	
		}
		if(allowMissingFeaturePatching){
			Concept missingFV = new DomainConceptEQ<Role, String>(new Role(f), KBVocabulary.FeatureValueMissingPatch);
			Concept toparse = Util.parseConceptFromGeneralRolePath(grp, KBVocabulary.CONCEPT_TOP);
			ConceptAssertion rhs = new ConceptAssertion(ca.getIndividual(), toparse);
			boolean addAnythingToCache = false;
			if(result.size()>0){
				//already obtained some f=v1 etc., so f=anything can be added without question
				addAnythingToCache = true;
			}else
			if(Util.assertionCheck(ca, rhs, kb)){
				//if no f is present in the assertion,check if f=MissingValuePatch, i.e., top is entailed
				addAnythingToCache = true;
			}
			if(addAnythingToCache){
				//add to cache
				if(ENABLE_CACHETREE){
					CacheTree.addCache(ca.getIndividual(), grp, missingFV);
				}
				//add to result
				result.add(missingFV);
//				result.add(KBVocabulary.CONCEPT_TOP);
			}
			
		}
		return result;
	}
	
	private enum Ops{
		LT, EQ, LTEQ
	}
	private Concept formDomainConcept(Role f,String s, Ops op){
		if(s.equals(KBVocabulary.FeatureValueMissingPatch)){
			if(allowMissingFeaturePatching){
				return KBVocabulary.CONCEPT_TOP;
			}
		}
		switch(op){
		case EQ:
			return new DomainConceptEQ<Role, String>(f, s);
		case LT:
			return new DomainConceptLT<Role, String>(f,s);
		case LTEQ:
			return new DomainConceptLTEQ<Role, String>(f,s);
		}
		return null;
	}

	//constants must be sorted lexicographically.
	private List<Concept> iterativeSearchK(ConceptAssertion ca, Role f, GeneralRolePath grp, 
			List<String> constants, int low, int high) {
		List<Concept> result = new LinkedList<Concept>();
		if(low > high){
			return result;
		}
		//i.e. floor value
		int mid = (low + high) >>> 1;
		Concept con;
		boolean end = low == high? true: false;
		if(end){
//			con = new DomainConceptEQ<Role, String>(f, constants.get(low));
			con = this.formDomainConcept(f, constants.get(low), Ops.EQ);
		}else if(high - low == 1){
			//if low and high differ only by 1.
			//then f=low or f=high as low<=f<=low+1
			con = new OrConcept(
					this.formDomainConcept(f, constants.get(low), Ops.EQ), 
					this.formDomainConcept(f, constants.get(high), Ops.EQ)
					);
		}
		else{
			// f>= low and f <= high
			con = new AndConcept(
					this.formDomainConcept(f, constants.get(high), Ops.LTEQ),
					new NotConcept(this.formDomainConcept(f, constants.get(low), Ops.LT))
			);
		}
		Concept test = Util.parseConceptFromGeneralRolePath(grp, con);
		ConceptAssertion rhs = new ConceptAssertion(ca.getIndividual(), test);
		if(Util.assertionCheck(ca, rhs, kb)){
			//System.out.println("true: "+ca +" -> "+rhs+"; \n low/high:"+low+"/"+high);
			if(end){
				if(ENABLE_CACHETREE){
					CacheTree.addCache(ca.getIndividual(), grp, con);
					//System.err.println("Cache entry -- "+ca.getIndividual()+rp+con);
				}
				result.add(con);
				//return result;
			}else{
				result.addAll(iterativeSearchK(ca, f, grp, constants, low, mid));
				result.addAll(iterativeSearchK(ca, f, grp, constants, mid+1, high));
			}
		}
		return result;
	}
	
	
//	
	private List<Concept> projectJoin(ConceptAssertion ca, ProjectionDescription pd1, 
			ProjectionDescription pd2, GeneralRolePath grp) throws ProjectionException {
		List<Concept> result = new LinkedList<Concept>();
		List<List<Concept>> loop = new LinkedList<List<Concept>>();
		loop.add(project(ca, pd2, grp));
		loop.add(project(ca, pd1, grp));
//		Concept top = Util.parseConcept("TOP");
		boolean toplevel = false;
		//top level join? only need to add most specific concepts
		if(grp.getOffset()==0){
			toplevel = true;
		}
		int i = 0;
		while(i<loop.size()){
			LinkedList<HashSet<Concept>> q = new LinkedList<HashSet<Concept>>();
			// initialize q
			for (Concept con : loop.get(i)) {
				HashSet<Concept> hs = new HashSet<Concept>();
				hs.add(con);
				q.add(hs);
				if(!toplevel){
					result.add(con);
				}
			}	
			for(HashSet<Concept> s2:q){
				int j = i+1;
				while(j<loop.size()){
					for(Concept d:loop.get(j)){
						HashSet<Concept> newcd = new HashSet<Concept>();
						newcd.addAll(s2);
						newcd.add(d);
						Concept cd = new AndConcept(newcd);
						Concept test = Util.parseConceptFromGeneralRolePath(grp, cd);
						ConceptAssertion rhs = new ConceptAssertion(ca.getIndividual(), test);
						if(Util.assertionCheck(ca, rhs, kb)){
							HashSet<Concept> hs = new HashSet<Concept>();
							hs.addAll(s2);
							hs.add(d);
							//add as result
							Concept cp = null;
							if(hs.size()>1){
								cp = new AndConcept(hs);
							}else{
								cp = hs.iterator().next();
							}
							result.add(cp);
						}
					}
					j++;
				}
				
			}
			i++;
		}
		return result;
	}
	

//	private List<Concept> projectJoin(ConceptAssertion ca, ProjectionDescription pd1, 
//			ProjectionDescription pd2, GeneralRolePath grp) throws ProjectionException {
//		List<Concept> result = new LinkedList<Concept>();
//		List<Concept> outer = project(ca, pd1, grp);
//		Concept top = Util.parseConcept("TOP");
//		if (outer.isEmpty()) {
//			outer.add(top);
//		}
//		for (Concept c1 : outer) {
////			c1 = testMissingFeatureValue(c1);
//			GeneralRolePath mygrp = grp.newCopy();
//			if (ENABLE_OPTIMIZATIONS) {
//				//rp.setConcept(c1);
//				mygrp.addContent(c1);
//			}
//			List<Concept> inner = project(ca, pd2, mygrp);
//			if (inner.isEmpty()) {
//				inner.add(top);
//			}
//			for (Concept in : inner) {
////				in = this.testMissingFeatureValue(in);
//				result.add(new AndConcept(c1, in));
//			}
////			grp.setConcept(null);
//		}
//		return result;
//	}
	
//	private Concept testMissingFeatureValue(Concept c1) {
//		if(allowMissingFeaturePatching){
//			if(c1 instanceof DomainConceptEQ){
//				String s = (String) ((DomainConceptEQ<?, ?>) c1).getRealValue();
//				if(s.equals(KBVocabulary.FeatureValueMissingPatch)){
//					return KBVocabulary.CONCEPT_TOP;
//				}
//			}
//		}
//		return c1;
//	}


	private List<Concept> projectRole(ConceptAssertion ca, String role, ProjectionDescription pd, 
			GeneralRolePath grp) throws ProjectionException {
		List<Concept> result = new LinkedList<Concept>();
		GeneralRolePath mygrp = grp.newCopy();
		mygrp.addContent(new Role(role));
		//because the join procedure produce maximum results, there is need to reduce s1 in advance
		List<Concept> s1 = project(ca, pd, mygrp);
		s1 = reduce(s1, grp, this.kb);
		s1 = reduce(s1, grp, null);
		// Empty inner result case
		if (s1.isEmpty()) {
			//Concept top = Util.parseConcept("TOP");
			Concept top = KBVocabulary.CONCEPT_TOP;
			Concept rhs = Util.parseConceptFromGeneralRolePath(mygrp, top);
			ConceptAssertion ast = new ConceptAssertion(ca.getIndividual(), rhs);
			if (Util.assertionCheck(ca, ast, kb)) {
				result.add(new ExistsConcept(new Role(role), top));
			}
			else {
				result.add(top);
			}
			return result;
		}
		
		// General case
		LinkedList<HashSet<Concept>> q = new LinkedList<HashSet<Concept>>();
		// initialize q
		for (Concept con : s1) {
			HashSet<Concept> hs = new HashSet<Concept>();
			hs.add(con);
			q.add(hs);
		}
		
		// build results
		while (!q.isEmpty()) {
			HashSet<Concept> s2 = q.removeLast();
			boolean notgrown = true;
			List<Concept> cans = getCandaditesLexographic(s1, s2);
			for (Concept can : cans) {
				HashSet<Concept> newSet = new HashSet<Concept>(s2);
				newSet.add(can);				
				Concept nested = null;
				if(newSet.size()>1){
					nested = new AndConcept(newSet);
				}else{
					nested = newSet.iterator().next();
				}
									
				Concept rhs = Util.parseConceptFromGeneralRolePath(mygrp, nested);
				ConceptAssertion ast = new ConceptAssertion(ca.getIndividual(), rhs);
				if (Util.assertionCheck(ca, ast, kb)) {
					q.add(newSet);
					notgrown = false;
				}
			}
			if (notgrown) {
				Concept filler = null;
				if(s2.size()>1){
					filler = new AndConcept(s2);
				}else{
					filler = s2.iterator().next();
				}
				result.add(new ExistsConcept(new Role(role), filler));
			}
		}
		return reduce(result, grp, this.kb);
	}
	
	// Get all 'cans' that are lexographically ordered after all constraints
	private static List<Concept> getCandaditesLexographic(List<Concept> cans, HashSet<Concept> constraints) {
		List<Concept> result = new LinkedList<Concept>();
		for (Concept c : cans) {
			boolean add = true;
			for (Concept d : constraints) {
				if (c.toString().compareTo(d.toString()) <= 0) {
					add = false;
					break;
				}
			}
			if (add) {
				result.add(c);
			}
		}
		return result;
	}
	

	// Reduce concept set to get most specific only
	private List<Concept> reduce(List<Concept> set, GeneralRolePath grp, DescriptionLogicsKB kb) {
		List<Concept> result = new LinkedList<Concept>();
		for (Concept c : set) {
			boolean minimal = true;
			for (Concept c2 : set) {
				if (c.equals(c2)) {
					continue;
				}				
				Concept lhs = Util.parseConceptFromGeneralRolePath(grp, c2);
				Concept rhs = Util.parseConceptFromGeneralRolePath(grp, c);	
//				System.out.println(lhs+"-->"+rhs);
				if (Util.subsumes(lhs, rhs, kb)) {
					if(Util.subsumes(rhs, lhs, kb)){
						if(ChooseLongestEqConcept){
							// if c2=c, choose the longest one.
							if(c2.toString().compareTo(c.toString())>0){
								minimal = false;
								break;
							}
						}
					}else{
						minimal = false;
						break;
					}
					
				}
			}
			if (minimal) {
				result.add(c);
			}
		}
		return result;
	}
	
}
